package gold.digger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC139 {

    /**
     * Input: s = "applepenapple", wordDict = ["apple", "pen"]
     * Output: true
     *
     * @param s
     * @param wordDict
     * @return
     */

    Map<String, Boolean> resDict = new HashMap<>();

    public boolean wordBreak(String str, List<String> wordDict) {
        if (null == wordDict || null == str || str.length() <= 0) {
            return false;
        }

        if (resDict.containsKey(str)) {
            return resDict.get(str);
        }

        for (String word : wordDict) {
            if (str.length() < word.length()) {
                continue;
            }

            String[] subStrList = str.split(word);
            if (subStrList.length == 1 && str.equals(subStrList[0])) {
                continue;
            }

            boolean curBreakWordOk = true;
            for (String subStr : subStrList) {
                if (subStr.length() <= 0) {
                    continue;
                }

                if (!wordBreak(subStr, wordDict)) {
                    curBreakWordOk = false;
                    break;
                }
            }

            if (curBreakWordOk) {
                resDict.put(str, true);
                return true;
            }
        }

        resDict.put(str, false);
        return false;
    }

    public static void main(String[] args) {
        LC139 an = new LC139();
        String s = "cars";
        List<String> wordDict = new ArrayList<>(Arrays.asList("car", "ca", "rs"));

        System.out.println(an.wordBreak(s, wordDict));
    }
}
